//dp[i][j]表示: p的[0, j]个字符是否能够匹配s的[0, i]个字符
//如果p[j]是一个普通字符
    //dp[i][j] = (p[j] == s[i] && dp[i - 1][j - 1])
//如果p[j] == '?'
    //dp[i][j] = dp[i - 1][j - 1]
//如果p[j] == '*'
    //如果p[j]匹配一个空串（不匹配s[i]）, dp[i][j] = dp[i][j - 1]
    //如果p[j]要进行匹配，那么'*'就可以匹配一个字符、两个字符、三个字符......
    //即dp[i][j] = dp[i - 1][j] || dp[i - 2][j] || dp[i - 3][j] || .....
    //令i = i - 1, dp[i - 1][j] = dp[i - 2][j] || dp[i - 3][j] || dp[i - 4][j] || .....
    //可得dp[i - 1][j] = dp[i - 2][j] || dp[i - 3][j] || .....
    //即dp[i][j] = dp[i - 1][j] || dp[i - 1][j]
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        s = "|" + s;
        p = "|" + p;

        dp[0][0] = true;    //空串可以匹配空串
        for (int i = 1; i < m + 1; i++)
        {
            if (p[i] == '*')
                dp[0][i] = true;
            else
                break;
        }

        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < m + 1; j++)
            {
                if (p[j] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p[j] == '*')
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else
                    dp[i][j] = (p[j] == s[i] && dp[i - 1][j - 1]);
            }
        }

        return dp[n][m];
    }
};